//
// Created by 紫霄 on 2020/4/18.
//

#ifndef LEETCODE_25_H
#define LEETCODE_25_H
//     输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
//
//     示例1：
//
//     输入：1->2->4, 1->3->4
//     输出：1->1->2->3->4->4
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
  ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode *ans = new ListNode(0);
    ListNode *cur = ans;
    while (l1 && l2) {
      if (l1->val > l2->val) {
        cur->next = l2;
        l2 = l2->next;
      } else {
        cur->next = l1;
        l1 = l1->next;
      }
      cur = cur->next;
    }
    if (l1) {
      cur->next = l1;
    }
    if (l2) {
      cur->next = l2;
    }
    return ans->next;
  }
};
#endif // LEETCODE_25_H
